home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2360 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: news.gate.net!pslfl2-37
  2. From: bhutto@gate.net (William Hutto)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: 20 Jan 1996 20:34:20 GMT
  6. Organization: CyberGate, Inc.
  7. Message-ID: <4drjkc$il4@news.gate.net>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca> <4dpian$gij@oxy.rust.net>
  9. NNTP-Posting-Host: pslfl2-37.gate.net
  10. X-Newsreader: News Xpress Version 1.0 Beta #4
  11.  
  12. In article <4dpian$gij@oxy.rust.net>, ebennett@rust.net spake:
  13. ;Bill Simpson <wsimpson@uwinnipeg.ca> wrote:
  14. ;
  15. ;>Is there a fast way to decide whether a number n is a power of 2?
  16. ;
  17. ;
  18. ;Working with positive numbers, a number will be a power of 2 if there
  19. ;is exactly one bit set in the number.  (For negative numbers, you can
  20. ;use the following by taking the abs() of the number).
  21.  
  22. Negative numbers? The person in question wasn't asking for a power of -2. 
  23. Power of 2 has to be > 0 for integers.
  24.  
  25. ;
  26. ;Given some number, there is a neat trick to generate a mask which will
  27. ;have exactly one bit set in it.  The bit set will be the least
  28. ;significant non-zero bit in the original number:
  29. ;
  30. ;    mask = ~number & number;
  31.  
  32. It's faster just to use:
  33.  
  34. mask = 0;
  35.  
  36. ;
  37. ;Now, if number contained a single non-zero bit (and is therefore a
  38. ;power of 2),  mask will be equal to number.  Therefore:
  39. ;
  40. ;   if (number == (~number & number))
  41.  
  42.     if(!number)
  43.  
  44. ;   {
  45. ;        /* number is a power of 2 */
  46.  
  47.     /* number == 0 */
  48.  
  49. ;   }
  50. ;
  51.  
  52. Bill
  53.  
  54. "Whatcha got on?...Your mind?"
  55.